# 257.二叉树的所有路径
# 给你一个二叉树的根节点root ，按任意顺序 ，返回所有从根节点到叶子节点的路径。
# 叶子节点是指没有子节点的节点。
#
#
# 示例1：
# 输入：root = [1, 2, 3, null, 5]
# 输出：["1->2->5", "1->3"]
#
# 示例2：
# 输入：root = [1]
# 输出：["1"]


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def binaryTreePaths(self, root):
        def traver(cur,path,result):
            path.append(cur.val) # 根，先加节点，再处理
            if cur.left == None and cur.right == None:
                tmp = [str(i)+'->' for i in path]
                s_path = "".join(tmp)[:-2] # 做字符串箭头
                result.append(s_path)
                return
            if cur.left:
                traver(cur.left,path,result)
                path.pop() # 回溯的过程即删除的过程
            if cur.right:
                traver(cur.right,path,result)
                path.pop() # 回溯的过程即删除的过程
        result = []
        path = []
        traver(root,path,result)
        return result

    def binaryTreePaths2(self, root: TreeNode):
        # 题目中节点数至少为1
        from collections import deque
        stack, path_st, result = deque([root]), deque(), []
        path_st.append(str(root.val))

        while stack:
            cur = stack.pop()
            path = path_st.pop()
            # 如果当前节点为叶子节点，添加路径到结果中
            if not (cur.left or cur.right):
                result.append(path)
            if cur.right:
                stack.append(cur.right)
                path_st.append(path + '->' + str(cur.right.val))
            if cur.left:
                stack.append(cur.left)
                path_st.append(path + '->' + str(cur.left.val))

        return result


if __name__ == '__main__':
    # 还有迭代法，这里先拿过来
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(9)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.binaryTreePaths(a11)
    print(res)
